#include <algorithm>
#include <cstdio>
#include <cstring>
const int N = 17;
int n, m, k;
int f[1 << (N - 1)], cnt[1 << (N - 1)];
bool vis[N][N];
int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
  freopen("prison.in", "r", stdin);
  freopen("prison.out", "w", stdout);
#endif
#endif

  scanf("%d%d%d", &n, &m, &k);
  int x, y;
  while (m--) {
    scanf("%d%d", &x, &y);
    vis[x][y] = vis[y][x] = true;
  }
  for (int tmp = 1; tmp < (1 << n); ++tmp)
    for (register int i = 1; i <= n; ++i) {
      if (tmp >> (i - 1) & 1)
        for (register int j = i + 1; j <= n; ++j) {
          if (tmp >> (j - 1) & 1)
            if (vis[i][j]) ++cnt[tmp];
        }
    }
  memset(f, 0x3f, sizeof(f));
  f[0] = 0;
  for (register int i = 1; i <= n; ++i) f[1 << (i - 1)] = 1;
  for (register int i = 0; i < (1 << n); ++i) {
    f[i] = (cnt[i] <= k) ? 1 : f[i];
    for (register int j = (i - 1) & i; j; j = (j - 1) & i) {
      f[i] = std::min(f[i], f[j] + ((cnt[i ^ j] <= k) ? 1 : f[i ^ j]));
    }
  }
  printf("%d", f[(1 << n) - 1]);
  return 0;
}